#include <stdio.h>

//二叉树的遍历
//构造树

typedef int TDataType;

typedef struct TreeNode
{
	TDataType data;
	struct TreeNode* left;
	struct TreeNode* right;
}TNode;

typedef struct Tree
{
	TNode* root;
	int size;
}Tree;


//后序遍历
int PostOrder(TNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	
	return PostOrder(root->left) + PostOrder(root->right) + 1;
}

int TreeKLevel(TNode* root, int depth)
{
	if (depth != 1 && root == NULL)
	{
		return 0;
	}
	
	if (depth == 1 && root == NULL)
	{
		return 0;
	}
	
	if (depth == 1 && root != NULL)
	{
		return 1;
	}
	
	return TreeKLevel(root->left, depth - 1) + TreeKLevel(root->right, depth - 1);
}

TNode* TreeFind(TNode* root, TDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	
	if (root->data == x)
	{
		return root;
	}
	
	TNode* res = TreeFind(root->left, x);
	if (res != NULL)
	{
		return res;
	}
	
	res = TreeFind(root->right, x);
	if (res != NULL)
	{
		return res;
	}
	
	return NULL;
}


int main()
{
	TNode t1 = {1, NULL, NULL};
	TNode t2 = {1, NULL, NULL};
	TNode t3 = {1, NULL, NULL};
	TNode t4 = {1, NULL, NULL};
	TNode t5 = {1, NULL, NULL};
	TNode t6 = {4, NULL, NULL};
	TNode t7 = {4, NULL, NULL};
	
	t1.left = &t2;
	t1.right = &t3;
	t2.left = &t4;
	t2.right = &t5;
	t3.right = &t6;
	t4.left = &t7;
	
	//printf("%d\n", ProOrder(&t1));
	//printf("%d\n", InOrder(&t1));
	printf("%d\n", PostOrder(&t1));
	
	printf("%d\n", TreeKLevel(&t1, 3));
	
	printf("%p\n", TreeFind(&t1, 4));
	printf("%p\n", &t7);
	
	return 0;
}
